Kuhn-Munkres配对算法

生活或工作中，我们常常碰到分配问题。比如公司有n个任务，由n个工人来做，每个工人不同程度地擅长一个或几个任务。如果你是管理层，如何布置任务最大程度地发挥大家所长使公司效率更高？又如，某相亲舞会，有n个俊男和n个靓女参加，每个靓女对不同气质和形象的俊男有不同好感度。如果你是主持人，如何分配跳舞伴侣使总体好感度最高？再如，奥运赛场上，乒乓球团体赛要求双方各出n名运动员一一角逐，取胜多的一方最终获胜。作为教练，你了解自己队员的实力以及战胜对方队员的把握，在已知对方出场顺序情况下，如何给出一个队员出场顺序使得最终获胜把握最大？

诸如此些问题，数学上抽象出来都是一个带权二分图的最优分配问题，这正是Kuhn-Munkres (KM)算法准备解决的问题。在了解这个算法之前，我们需要粗略掌握一些图论基础。为简单起见，笔者尽量避免课本上晦涩深奥的数学定义和符号，使用通俗易懂的语言。

图(Graph, G)是由一组顶点(Vertex, V)以及顶点与顶点之间的连线(称作边(Edge, E))构成，记为G(V, E)，如图1(a)所示。边如果有方向则为有向图(Directed Graph)，否则为无向图(Undirected Graph)。同样地，边上也可能带有权重，相应的图称为带权图(Weighted Graph)。子图与图的关系相当于子集与集合的关系，由图的部分组成。生成子图(Spanning Subgraph)是包含所有顶点但未必包含所有边(即V(G*)=V(G))的子图；而导出子图(Induced Subgraph)是部分顶点（或边）及其关联的边（或顶点）所组成的子图。

图 1. 图(a)和二分图(b)

二分图(Bipartite Graph)通俗意义上是顶点被分成两不相交集合且边横跨在这两集合的无向图。上图1(a)其实也是一个二分图（见图1(b)）。匹配(Matching)是二分图中无公共顶点的边的集合。如图2(a)所示，在这个匹配子图中，假设暂时只含有一条匹配边e_1-5，用红色表示，其它绿色边都是未匹配边。最大匹配(Maximum Matching)是边数最多的匹配。完备匹配(Perfect Matching)是所有顶点都被匹配的匹配。交错路(Alternating Path)是一条从未匹配顶点出发，依次经过非匹配边、匹配边…形成的路径，如图2(b)所示，其中2→5→1→6就是一条交错路（未匹配边用红色虚线表示）。增广路(Augmenting Path)是从一个未匹配顶点出发，走交替路，到达另一个未匹配顶点的路径。图2(b)中，2→5→1→6也是一条增广路。

图2. 匹配(a)和交错路及增广路(b)和新匹配(c)

仔细观察增广路，我们可以发现，增广路共有奇数条边，且非匹配边比匹配边多一条，奇数边未匹配，而偶数边已匹配。因此，如果我们将增广路取反（即未匹配变匹配，匹配变未匹配），新得到的匹配（图2(c)）比原匹配（图2(a)）多出了一条边，即匹配被改进了。如此反复进行下去，到再也找不出增广路时就达到最大匹配（增广路原理）。

在上述最大匹配算法中，搜寻增广路可以采用两种方法，深度优先搜索(Depth-First Search, DFS)和广度优先搜索(Breadth-First Search, BFS)。DFS递归纵向进行，思路清晰，代码少。BFS按层横向进行，需要手动维护一个队列，略麻烦。对稠密图，两者不相上下，但对稀疏图，BFS快于DFS。简单的最大匹配算法每次只搜寻一条增广路径，其时间标度为O(VE)。一个改进的方法是每次搜寻多条增广路径，按其中极大路径增广，可以证明，这样最多增广E^0.5次即可达到最大匹配，即标度为O(VE^0.5)，这就是Hopcroft-Karp算法。

最大匹配算法是尽可能多地寻找匹配，但寻找的匹配未必是最优的。

一个匹配的优劣可以用边权表示，即给边赋上权重，这样的二分图称为带权二分图。比如权重表（表1）赋给二分图（图1(a)）得到如图3这样的带权二分图。边权的现实意义是一个员工对业务的熟悉程度，或者舞会上靓女对男伴的好感程度，最优匹配就是要使匹配后总熟悉度或总好感度最高，即总权最大(maximum-weighted matching)。KM算法就是一个求解带权二分图最优匹配(Optimal Matching)的算法。

表1. 三对三的一个权重表

		task
		4	5	6
worker	1	2.0	1.0	3.0
2	1.0	0.0	2.0
3	2.0	2.0	3.0

图3. 带权二分图

由上可知，最优匹配是在匹配的基础上考虑了权重，或者换个角度，完备匹配可以看作是一种等权的特殊最优匹配。因此可以通过某种方式转化最优匹配为完备匹配，然后利用已知的最大匹配算法求解。KM算法正是利用了这个思想。

在KM算法中，每个顶点分配一个指标，称作顶标(Vertex Labeling)，用l表示。比如由工人S和任务T两个集合组成顶点、表1构成边权矩阵W的带权二分图(图3)，左侧工人S集各顶点取最大边权为顶标，右侧任务T集各顶点的顶标赋0.0，如图4(a)所示。满足l_s+l_t≥W_st, s∈S, t∈T的顶标是可行的，叫做可行顶标(Feasible Vertex Labeling)。此时，对于l_s+l_t=W_st, s∈S, t∈T的子图G*称为相等子图。

图4. 可行顶标及相等子图(a)、寻找完备匹配(b)和修改顶标(c)

相等子图的重要意义在于其完备匹配就是图的最优匹配，这依据在于Kuhn-Munkres定理。这个定理很显然，因为一个匹配包含于相等子图，那么它的边权和必等于所有顶点的顶标和；如果存在某边不包含于相等子图，其必不是完备匹配，边权和必小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最优匹配。因此我们只要找到相等子图的完备匹配就找到了图的最优匹配。如果遇到冲突，找不到完备匹配，修订顶标继续找，直到找到为止。如何修订顶标？那就是，增广路上左侧S集各点减去一小量δ而右侧T集各点增加一小量δ，使得新边加入相等子图扩大、逐步变得完备。小量δ通常取

以至加入的新边是匹配的最佳选择。

下面以图3二分图的最大权匹配为例具体说明KM算法流程：

(1) 初始化可行顶标。初始化时，左侧各顶标取最大边权，右侧各顶标设为0.0。这步其实我们已经做了，结果如图4(a)。

(2) 寻找完备匹配。用上述的最大匹配算法搜寻完备匹配，如果找到，结束程序；否则转到第3步。搜寻完备匹配时，以次为左侧各顶点找增广路。如图4(b)所示，首先从1开始，为1找到增广路1→6，即1匹配到6。接着为2找增广路，但6已匹配1，遇到冲突，不能找到完备匹配。

(3) 修订可行顶标。在上步寻找完备匹配时，为2找增广路（2→6→1→?）不能完成，此时需要修改顶标让新边加入匹配。那么如何修改顶标使新边加入？如图4(b)所示，现在有两个选择，一是让e_1-4边加入，二是让e_2-4边（某些情况下可以是e_2-5边）加入。因为最终要求的是最大权匹配，我们应尽量让差别最小的权边加入，所以

。

因此，顶标修改应遵循以下原则

即增广路上左侧S集各点减去小量δ，右侧T集各点增加小量δ，这样做的目的是保证新边加入后相等子图仍然保持。如图4(c)所示，左侧顶点1的顶标从3.0变为2.0，2的顶标从2.0变为1.0，而右侧顶点6的顶标从0.0增加到1.0。另外，我们也可以看到，对e_1-6边来说，l₁(2.0) + l₆(1.0) = W₁₆(3.0)；对e_2-6边来说，同样l₂(1.0) + l₆(1.0) = W₂₆(2.0)，所以相等子图仍然保持。同时，我们也可以看到，对顶点1， e_1-4边可以匹配，因为l₁(2.0) + l₄(0.0) = W₁₄(2.0)；对顶点2，e_2-4边也可以匹配，因为l₂(1.0) + l₄(0.0) = W₁₄(1.0)。所以经过顶标修改，两条权边可以加入相等子图，相等子图被扩大。注意，这里事实上是一种贪心算法的体现。我们可以粗略地将初始化匹配理解为此二分图可能（多数情况下它不是）的一个最大权匹配，因为初始化时我们总是为各顶点取最大边权为顶标，而在接下来每次修改顶标过程中，我们总是让顶标减小最小，这样每次减小最小就能保证最终就是边权最大的匹配。

(4) 重复2、3步直到找到最优匹配。修订顶标后，现在重新寻找完备匹配，为1找到匹配6，为2找到匹配4，为3找匹配，发现6已被匹配，又遇到冲突，再修改顶标，最终可为3找到匹配5。所以最终的最优匹配为{1→6，2→4，3→5}。

再举一个更大的例子，比如一个10×10的分配问题，其权重矩阵如下：

对于这样一个分配，利用上述算法可以快速轻易得到最终的最优匹配：{1→9，2→7，3→2，4→3，5→8，6→6，7→4，8→10，9→5，10→1}。

需要注意的是，减小量δ的计算那步需要N²操作，使得KM算法的复杂度达到O(N⁴)。所以，我们可以利用一个数组将l_s+l_t−W_st存储起来，修改顶标时把数组相应变动，这样KM算法的复杂度降到O(N³)。

综上所述，KM算法是解决带权二分图最优匹配的一个算法，其核心思想是，通过定义顶标引入相等子图，而相等子图的完备匹配就是一个最优匹配，这样最优匹配问题就巧妙地转化成了完备匹配问题，只要不断修订顶标扩大相等子图，利用已知的最大匹配算法就能找到最终的最优匹配。

应用此算法我们可以解决许多配对问题。比如，离子液体中单个阴离子或阳离子带有电荷不便描述，若配对组成不带电荷的离子对，计算就变得容易[Phys. Chem. Chem. Phys., 2018, 20, 13547]；又如，广义价键(Generalized Valence Bond, GVB)计算要求成键轨道与反键轨道配对成轨道对，对小型体系人们尚且可以手动完成，但对稍大的复杂体系，这几乎是不可能完成的，利用KM算法我们可以实现GVB轨道的自动配对[J. Chem. Theory Comput., 2019, 15, 141]。在后面的推送中我们还会有详细介绍，敬请期待！

参考资料

[1] 李建中, 图论导引. 机械工业出版社. 2001.

[2] 徐六通, 杨娟, 吴斌译. 离散数学及其应用. 2014.

[3] 徐丹, 吴伟敏. C++数据结构与算法. 2014.

[4] Kuhn, H. W., The Hungarian method for the assignment problem. Nav. Res. Logist. 1955, 2 (1-2), 83-97.

[5] Munkres, J., Algorithms for the Assignment and Transportation Problems. J. Soc. Ind. Appl. Math. 1957, 5 (1), 32-38.

[6] Hopcroft, J. E.; Karp, R. M., An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing 1973, 2 (4), 225-231.

[7] Crouse, D. F., On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems 2016, 52 (4), 1679-1696.

[8] https://brilliant.org/wiki/hungarian-matching/